package DepthFirstSearch;

public class _130_SurroundedRegions {
    char[][] board;
    boolean[][] check;
    boolean[][] tag;
    int length;
    int width;
    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) {
            return;
        }
        this.board = board;
        this.length = board.length;
        this.width = board[0].length;
        this.check = new boolean[length][width];
        this.tag = new boolean[length][width];
        for (int i = 0; i < length; i++) {
            dfs(i, 0);
            dfs(i, width - 1);
        }
        for (int i = 0; i < width; i++) {
            dfs(0, i);
            dfs(length - 1, i);
        }
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < width; j++) {
                if (board[i][j] == 'O' && !tag[i][j]) {
                    board[i][j] = 'X';
                }
            } 
        }
    }

    public void dfs(int row, int column) {
        if (row >= length || column >= width || row < 0 || column < 0) {
            return;
        }
        if (!check[row][column]) {
            check[row][column] = true;
            if (board[row][column] == 'O') {
                tag[row][column] = true;
                dfs(row + 1, column);
                dfs(row - 1, column);
                dfs(row, column + 1);
                dfs(row, column - 1);
            }
        }
    }
}
